package com.hejing.排序算法;

import java.text.SimpleDateFormat;
import java.util.Date;

public class MergeSort {
    public static void main(String[] args) {
        // int[] arr = {1, -1, 90, 31, 922, -102, 0, 221, 441, -100};

        int count = 8000000;
        int[] arr = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = (int)(Math.random() *  10000000);
        }

        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Date date1 = new Date();
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间: " + date1Str);
        // System.out.println("排序前的数组: " + Arrays.toString(arr));

        mergeSort(arr);

        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间:" + date2Str);
        // System.out.println("排序后的数组: " + Arrays.toString(arr));
    }

    // 二路归并排序-递归法实现
    public static void mergeSort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];  // 临时储存排序结果的数组
        mergeSortRecursion(arr, result, 0, len - 1);
    }

    /**
     * 二路归并-递归法实现
     * @param arr  待排序数组
     * @param result  临时储存排序结果的数组
     * @param start  起始下标
     * @param end 结束下标
     */
    private static void mergeSortRecursion(int[] arr, int[] result, int start, int end) {
        // 设置递归结束条件:
        if (start >= end) {
            return;
        }
        int len = (end - start);  // 数组长度
        int mid = (len >> 1) + start;  // 中位下标
        int start1 = start;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = end;

        // 指向临时数组当前的索引
        int i = start;

        // 递归分解左边数组
        mergeSortRecursion(arr, result, start1, end1);
        // 递归分解右边的数组
        mergeSortRecursion(arr, result, start2, end2);

        // 分解到只有一个元素之后
        // 开始进行归并操作
        while(start1 <= end1 && start2 <= end2) {
            result[i++] = arr[start1] < arr[start2] ? arr[start1++]: arr[start2++];
        }
        while (start1 <= end1) {  // start2所在数组先结束
            result[i++] = arr[start1++];
        }
        while (start2 <= end2) {  // start1所在数组先结束
            result[i++] = arr[start2++];
        }
        // 此时result储存的序列就是有序序列，将之一一复制到原数组中即可。
        for (i = start; i <= end; i++) {
            arr[i] = result[i];
        }
    }
}




























